// ImageEncoder - abstract class for writing out an image
// http://www.acme.com/java/software/Acme.JPM.Encoders.ImageEncoder.html
//
// Copyright (C) 1996 by Jef Poskanzer <jef@acme.com>.  All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// Visit the ACME Labs Java page for up-to-date versions of this and other
// fine Java utilities: http://www.acme.com/java/

package com.jgraph.pad.util;

import java.awt.Image;
import java.awt.image.ColorModel;
import java.awt.image.ImageConsumer;
import java.awt.image.ImageProducer;
import java.io.IOException;
import java.io.OutputStream;
import java.util.Dictionary;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.NoSuchElementException;

/// Abstract class for writing out an image.
// <P>
// A framework for classes that encode and write out an image in
// a particular file format.
// <P>
// This provides a simplified rendition of the ImageConsumer interface.
// It always delivers the pixels as ints in the RGBdefault color model.
// It always provides them in top-down left-right order.
// If you want more flexibility you can always implement ImageConsumer
// directly.
// <P>
// <A HREF="/resources/classes/Acme/JPM/Encoders/ImageEncoder.java">Fetch the software.</A><BR>
// <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
// <P>
// @see GifEncoder
// @see PpmEncoder
// @see Acme.JPM.Decoders.ImageDecoder

public abstract class JGraphpadImageEncoder implements ImageConsumer {

	protected OutputStream out;

	private ImageProducer producer;

	private int width = -1;

	private int height = -1;

	private int hintflags = 0;

	private boolean started = false;

	private boolean encoding;

	private IOException iox;

	private static final ColorModel rgbModel = ColorModel.getRGBdefault();

	private Hashtable props = null;

	// / Constructor.
	// @param img The image to encode.
	// @param out The stream to write the bytes to.
	public JGraphpadImageEncoder(Image img, OutputStream out)
			throws IOException {
		this(img.getSource(), out);
	}

	// / Constructor.
	// @param producer The ImageProducer to encode.
	// @param out The stream to write the bytes to.
	public JGraphpadImageEncoder(ImageProducer producer, OutputStream out)
			throws IOException {
		this.producer = producer;
		this.out = out;
	}

	/**
	 * Public GIF Encoding method. Use this method for GIF encoding in JGraph
	 * editors.
	 * 
	 * @throws IOException
	 */
	public static void writeGIF(Image image, OutputStream out)
			throws IOException {
		new GifEncoder(image, out).encode();
	}

	// Methods that subclasses implement.

	// / Subclasses implement this to initialize an encoding.
	abstract void encodeStart(int w, int h) throws IOException;

	// / Subclasses implement this to actually write out some bits. They
	// are guaranteed to be delivered in top-down-left-right order.
	// One int per pixel, index is row * scansize + off + col,
	// RGBdefault (AARRGGBB) color model.
	abstract void encodePixels(int x, int y, int w, int h, int[] rgbPixels,
			int off, int scansize) throws IOException;

	// / Subclasses implement this to finish an encoding.
	abstract void encodeDone() throws IOException;

	// Our own methods.

	// / Call this after initialization to get things going.
	public synchronized void encode() throws IOException {
		encoding = true;
		iox = null;
		producer.startProduction(this);
		while (encoding)
			try {
				wait();
			} catch (InterruptedException e) {
			}
		if (iox != null)
			throw iox;
	}

	private boolean accumulate = false;

	private int[] accumulator;

	private void encodePixelsWrapper(int x, int y, int w, int h,
			int[] rgbPixels, int off, int scansize) throws IOException {
		if (!started) {
			started = true;
			encodeStart(width, height);
			if ((hintflags & TOPDOWNLEFTRIGHT) == 0) {
				accumulate = true;
				accumulator = new int[width * height];
			}
		}
		if (accumulate)
			for (int row = 0; row < h; ++row)
				System.arraycopy(rgbPixels, row * scansize + off, accumulator,
						(y + row) * width + x, w);
		else
			encodePixels(x, y, w, h, rgbPixels, off, scansize);
	}

	private void encodeFinish() throws IOException {
		if (accumulate) {
			encodePixels(0, 0, width, height, accumulator, 0, width);
			accumulator = null;
			accumulate = false;
		}
	}

	private synchronized void stop() {
		encoding = false;
		notifyAll();
	}

	// Methods from ImageConsumer.

	public void setDimensions(int width, int height) {
		this.width = width;
		this.height = height;
	}

	public void setProperties(Hashtable props) {
		this.props = props;
	}

	public void setColorModel(ColorModel model) {
		// Ignore.
	}

	public void setHints(int hintflags) {
		this.hintflags = hintflags;
	}

	public void setPixels(int x, int y, int w, int h, ColorModel model,
			byte[] pixels, int off, int scansize) {
		int[] rgbPixels = new int[w];
		for (int row = 0; row < h; ++row) {
			int rowOff = off + row * scansize;
			for (int col = 0; col < w; ++col)
				rgbPixels[col] = model.getRGB(pixels[rowOff + col] & 0xff);
			try {
				encodePixelsWrapper(x, y + row, w, 1, rgbPixels, 0, w);
			} catch (IOException e) {
				iox = e;
				stop();
				return;
			}
		}
	}

	public void setPixels(int x, int y, int w, int h, ColorModel model,
			int[] pixels, int off, int scansize) {
		if (model == rgbModel) {
			try {
				encodePixelsWrapper(x, y, w, h, pixels, off, scansize);
			} catch (IOException e) {
				iox = e;
				stop();
				return;
			}
		} else {
			int[] rgbPixels = new int[w];
			for (int row = 0; row < h; ++row) {
				int rowOff = off + row * scansize;
				for (int col = 0; col < w; ++col)
					rgbPixels[col] = model.getRGB(pixels[rowOff + col]);
				try {
					encodePixelsWrapper(x, y + row, w, 1, rgbPixels, 0, w);
				} catch (IOException e) {
					iox = e;
					stop();
					return;
				}
			}
		}
	}

	public void imageComplete(int status) {
		producer.removeConsumer(this);
		if (status == ImageConsumer.IMAGEABORTED)
			iox = new IOException("image aborted");
		else {
			try {
				encodeFinish();
				encodeDone();
			} catch (IOException e) {
				iox = e;
			}
		}
		stop();
	}

	public static class GifEncoder extends JGraphpadImageEncoder {

		private boolean interlace = false;

		// / Constructor from Image.
		// @param img The image to encode.
		// @param out The stream to write the GIF to.
		public GifEncoder(Image img, OutputStream out) throws IOException {
			super(img, out);
		}

		// / Constructor from Image with interlace setting.
		// @param img The image to encode.
		// @param out The stream to write the GIF to.
		// @param interlace Whether to interlace.
		public GifEncoder(Image img, OutputStream out, boolean interlace)
				throws IOException {
			super(img, out);
			this.interlace = interlace;
		}

		// / Constructor from ImageProducer.
		// @param prod The ImageProducer to encode.
		// @param out The stream to write the GIF to.
		public GifEncoder(ImageProducer prod, OutputStream out)
				throws IOException {
			super(prod, out);
		}

		// / Constructor from ImageProducer with interlace setting.
		// @param prod The ImageProducer to encode.
		// @param out The stream to write the GIF to.
		public GifEncoder(ImageProducer prod, OutputStream out,
				boolean interlace) throws IOException {
			super(prod, out);
			this.interlace = interlace;
		}

		int width, height;

		int[][] rgbPixels;

		void encodeStart(int width, int height) throws IOException {
			this.width = width;
			this.height = height;
			rgbPixels = new int[height][width];
		}

		void encodePixels(int x, int y, int w, int h, int[] rgbPixels, int off,
				int scansize) throws IOException {
			// Save the pixels.
			for (int row = 0; row < h; ++row)
				System.arraycopy(rgbPixels, row * scansize + off,
						this.rgbPixels[y + row], x, w);

		}

		IntHashtable colorHash;

		void encodeDone() throws IOException {
			int transparentIndex = -1;
			int transparentRgb = -1;
			// Put all the pixels into a hash table.
			colorHash = new IntHashtable();
			int index = 0;
			for (int row = 0; row < height; ++row) {
				for (int col = 0; col < width; ++col) {
					int rgb = rgbPixels[row][col];
					boolean isTransparent = ((rgb >>> 24) < 0x80);
					if (isTransparent) {
						if (transparentIndex < 0) {
							// First transparent color; remember it.
							transparentIndex = index;
							transparentRgb = rgb;
						} else if (rgb != transparentRgb) {
							// A second transparent color; replace it with
							// the first one.
							rgbPixels[row][col] = rgb = transparentRgb;
						}
					}
					GifEncoderHashitem item = (GifEncoderHashitem) colorHash
							.get(rgb);
					if (item == null) {
						if (index >= 256)
							throw new IOException("too many colors for a GIF");
						item = new GifEncoderHashitem(rgb, 1, index,
								isTransparent);
						++index;
						colorHash.put(rgb, item);
					} else
						++item.count;
				}
			}

			// Figure out how many bits to use.
			int logColors;
			if (index <= 2)
				logColors = 1;
			else if (index <= 4)
				logColors = 2;
			else if (index <= 16)
				logColors = 4;
			else
				logColors = 8;

			// Turn colors into colormap entries.
			int mapSize = 1 << logColors;
			byte[] reds = new byte[mapSize];
			byte[] grns = new byte[mapSize];
			byte[] blus = new byte[mapSize];
			for (Enumeration e = colorHash.elements(); e.hasMoreElements();) {
				GifEncoderHashitem item = (GifEncoderHashitem) e.nextElement();
				reds[item.index] = (byte) ((item.rgb >> 16) & 0xff);
				grns[item.index] = (byte) ((item.rgb >> 8) & 0xff);
				blus[item.index] = (byte) (item.rgb & 0xff);
			}

			GIFEncode(out, width, height, interlace, (byte) 0,
					transparentIndex, logColors, reds, grns, blus);
		}

		byte GetPixel(int x, int y) throws IOException {
			GifEncoderHashitem item = (GifEncoderHashitem) colorHash
					.get(rgbPixels[y][x]);
			if (item == null)
				throw new IOException("color not found");
			return (byte) item.index;
		}

		static void writeString(OutputStream out, String str)
				throws IOException {
			byte[] buf = str.getBytes();
			out.write(buf);
		}

		// Adapted from ppmtogif, which is based on GIFENCOD by David
		// Rowley <mgardi@watdscu.waterloo.edu>. Lempel-Zim compression
		// based on "compress".

		int Width, Height;

		boolean Interlace;

		int curx, cury;

		int CountDown;

		int Pass = 0;

		void GIFEncode(OutputStream outs, int Width, int Height,
				boolean Interlace, byte Background, int Transparent,
				int BitsPerPixel, byte[] Red, byte[] Green, byte[] Blue)
				throws IOException {
			byte B;
			int LeftOfs, TopOfs;
			int ColorMapSize;
			int InitCodeSize;
			int i;

			this.Width = Width;
			this.Height = Height;
			this.Interlace = Interlace;
			ColorMapSize = 1 << BitsPerPixel;
			LeftOfs = TopOfs = 0;

			// Calculate number of bits we are expecting
			CountDown = Width * Height;

			// Indicate which pass we are on (if interlace)
			Pass = 0;

			// The initial code size
			if (BitsPerPixel <= 1)
				InitCodeSize = 2;
			else
				InitCodeSize = BitsPerPixel;

			// Set up the current x and y position
			curx = 0;
			cury = 0;

			// Write the Magic header
			writeString(outs, "GIF89a");

			// Write out the screen width and height
			Putword(Width, outs);
			Putword(Height, outs);

			// Indicate that there is a global colour map
			B = (byte) 0x80; // Yes, there is a color map
			// OR in the resolution
			B |= (byte) ((8 - 1) << 4);
			// Not sorted
			// OR in the Bits per Pixel
			B |= (byte) ((BitsPerPixel - 1));

			// Write it out
			Putbyte(B, outs);

			// Write out the Background colour
			Putbyte(Background, outs);

			// Pixel aspect ratio - 1:1.
			// Putbyte( (byte) 49, outs );
			// Java's GIF reader currently has a bug, if the aspect ratio byte
			// is
			// not zero it throws an ImageFormatException. It doesn't know that
			// 49 means a 1:1 aspect ratio. Well, whatever, zero works with all
			// the other decoders I've tried so it probably doesn't hurt.
			Putbyte((byte) 0, outs);

			// Write out the Global Colour Map
			for (i = 0; i < ColorMapSize; ++i) {
				Putbyte(Red[i], outs);
				Putbyte(Green[i], outs);
				Putbyte(Blue[i], outs);
			}

			// Write out extension for transparent colour index, if necessary.
			if (Transparent != -1) {
				Putbyte((byte) '!', outs);
				Putbyte((byte) 0xf9, outs);
				Putbyte((byte) 4, outs);
				Putbyte((byte) 1, outs);
				Putbyte((byte) 0, outs);
				Putbyte((byte) 0, outs);
				Putbyte((byte) Transparent, outs);
				Putbyte((byte) 0, outs);
			}

			// Write an Image separator
			Putbyte((byte) ',', outs);

			// Write the Image header
			Putword(LeftOfs, outs);
			Putword(TopOfs, outs);
			Putword(Width, outs);
			Putword(Height, outs);

			// Write out whether or not the image is interlaced
			if (Interlace)
				Putbyte((byte) 0x40, outs);
			else
				Putbyte((byte) 0x00, outs);

			// Write out the initial code size
			Putbyte((byte) InitCodeSize, outs);

			// Go and actually compress the data
			compress(InitCodeSize + 1, outs);

			// Write out a Zero-length packet (to end the series)
			Putbyte((byte) 0, outs);

			// Write the GIF file terminator
			Putbyte((byte) ';', outs);
		}

		// Bump the 'curx' and 'cury' to point to the next pixel
		void BumpPixel() {
			// Bump the current X position
			++curx;

			// If we are at the end of a scan line, set curx back to the
			// beginning
			// If we are interlaced, bump the cury to the appropriate spot,
			// otherwise, just increment it.
			if (curx == Width) {
				curx = 0;

				if (!Interlace)
					++cury;
				else {
					switch (Pass) {
					case 0:
						cury += 8;
						if (cury >= Height) {
							++Pass;
							cury = 4;
						}
						break;

					case 1:
						cury += 8;
						if (cury >= Height) {
							++Pass;
							cury = 2;
						}
						break;

					case 2:
						cury += 4;
						if (cury >= Height) {
							++Pass;
							cury = 1;
						}
						break;

					case 3:
						cury += 2;
						break;
					}
				}
			}
		}

		static final int EOF = -1;

		// Return the next pixel from the image
		int GIFNextPixel() throws IOException {
			byte r;

			if (CountDown == 0)
				return EOF;

			--CountDown;

			r = GetPixel(curx, cury);

			BumpPixel();

			return r & 0xff;
		}

		// Write out a word to the GIF file
		void Putword(int w, OutputStream outs) throws IOException {
			Putbyte((byte) (w & 0xff), outs);
			Putbyte((byte) ((w >> 8) & 0xff), outs);
		}

		// Write out a byte to the GIF file
		void Putbyte(byte b, OutputStream outs) throws IOException {
			outs.write(b);
		}

		// GIFCOMPR.C - GIF Image compression routines
		//
		// Lempel-Ziv compression based on 'compress'. GIF modifications by
		// David Rowley (mgardi@watdcsu.waterloo.edu)

		// General DEFINEs

		static final int BITS = 12;

		static final int HSIZE = 5003; // 80% occupancy

		// GIF Image compression - modified 'compress'
		//
		// Based on: compress.c - File compression ala IEEE Computer, June 1984.
		//
		// By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
		// Jim McKie (decvax!mcvax!jim)
		// Steve Davies (decvax!vax135!petsd!peora!srd)
		// Ken Turkowski (decvax!decwrl!turtlevax!ken)
		// James A. Woods (decvax!ihnp4!ames!jaw)
		// Joe Orost (decvax!vax135!petsd!joe)

		int n_bits; // number of bits/code

		int maxbits = BITS; // user settable max # bits/code

		int maxcode; // maximum code, given n_bits

		int maxmaxcode = 1 << BITS; // should NEVER generate this code

		final int MAXCODE(int n_bits) {
			return (1 << n_bits) - 1;
		}

		int[] htab = new int[HSIZE];

		int[] codetab = new int[HSIZE];

		int hsize = HSIZE; // for dynamic table sizing

		int free_ent = 0; // first unused entry

		// block compression parameters -- after all codes are used up,
		// and compression rate changes, start over.
		boolean clear_flg = false;

		// Algorithm: use open addressing double hashing (no chaining) on the
		// prefix code / next character combination. We do a variant of Knuth's
		// algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
		// secondary probe. Here, the modular division first probe is gives way
		// to a faster exclusive-or manipulation. Also do block compression with
		// an adaptive reset, whereby the code table is cleared when the
		// compression
		// ratio decreases, but after the table fills. The variable-length
		// output
		// codes are re-sized at this point, and a special CLEAR code is
		// generated
		// for the decompressor. Late addition: construct the table according to
		// file size for noticeable speed improvement on small files. Please
		// direct
		// questions about this implementation to ames!jaw.

		int g_init_bits;

		int ClearCode;

		int EOFCode;

		void compress(int init_bits, OutputStream outs) throws IOException {
			int fcode;
			int i /* = 0 */;
			int c;
			int ent;
			int disp;
			int hsize_reg;
			int hshift;

			// Set up the globals: g_init_bits - initial number of bits
			g_init_bits = init_bits;

			// Set up the necessary values
			clear_flg = false;
			n_bits = g_init_bits;
			maxcode = MAXCODE(n_bits);

			ClearCode = 1 << (init_bits - 1);
			EOFCode = ClearCode + 1;
			free_ent = ClearCode + 2;

			char_init();

			ent = GIFNextPixel();

			hshift = 0;
			for (fcode = hsize; fcode < 65536; fcode *= 2)
				++hshift;
			hshift = 8 - hshift; // set hash code range bound

			hsize_reg = hsize;
			cl_hash(hsize_reg); // clear hash table

			output(ClearCode, outs);

			outer_loop: while ((c = GIFNextPixel()) != EOF) {
				fcode = (c << maxbits) + ent;
				i = (c << hshift) ^ ent; // xor hashing

				if (htab[i] == fcode) {
					ent = codetab[i];
					continue;
				} else if (htab[i] >= 0) // non-empty slot
				{
					disp = hsize_reg - i; // secondary hash (after G. Knott)
					if (i == 0)
						disp = 1;
					do {
						if ((i -= disp) < 0)
							i += hsize_reg;

						if (htab[i] == fcode) {
							ent = codetab[i];
							continue outer_loop;
						}
					} while (htab[i] >= 0);
				}
				output(ent, outs);
				ent = c;
				if (free_ent < maxmaxcode) {
					codetab[i] = free_ent++; // code -> hashtable
					htab[i] = fcode;
				} else
					cl_block(outs);
			}
			// Put out the final code.
			output(ent, outs);
			output(EOFCode, outs);
		}

		// output
		//
		// Output the given code.
		// Inputs:
		// code: A n_bits-bit integer. If == -1, then EOF. This assumes
		// that n_bits =< wordsize - 1.
		// Outputs:
		// Outputs code to the file.
		// Assumptions:
		// Chars are 8 bits long.
		// Algorithm:
		// Maintain a BITS character long buffer (so that 8 codes will
		// fit in it exactly). Use the VAX insv instruction to insert each
		// code in turn. When the buffer fills up empty it and start over.

		int cur_accum = 0;

		int cur_bits = 0;

		int masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F,
				0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF,
				0x7FFF, 0xFFFF };

		void output(int code, OutputStream outs) throws IOException {
			cur_accum &= masks[cur_bits];

			if (cur_bits > 0)
				cur_accum |= (code << cur_bits);
			else
				cur_accum = code;

			cur_bits += n_bits;

			while (cur_bits >= 8) {
				char_out((byte) (cur_accum & 0xff), outs);
				cur_accum >>= 8;
				cur_bits -= 8;
			}

			// If the next entry is going to be too big for the code size,
			// then increase it, if possible.
			if (free_ent > maxcode || clear_flg) {
				if (clear_flg) {
					maxcode = MAXCODE(n_bits = g_init_bits);
					clear_flg = false;
				} else {
					++n_bits;
					if (n_bits == maxbits)
						maxcode = maxmaxcode;
					else
						maxcode = MAXCODE(n_bits);
				}
			}

			if (code == EOFCode) {
				// At EOF, write the rest of the buffer.
				while (cur_bits > 0) {
					char_out((byte) (cur_accum & 0xff), outs);
					cur_accum >>= 8;
					cur_bits -= 8;
				}

				flush_char(outs);
			}
		}

		// Clear out the hash table

		// table clear for block compress
		void cl_block(OutputStream outs) throws IOException {
			cl_hash(hsize);
			free_ent = ClearCode + 2;
			clear_flg = true;

			output(ClearCode, outs);
		}

		// reset code table
		void cl_hash(int hsize) {
			for (int i = 0; i < hsize; ++i)
				htab[i] = -1;
		}

		// GIF Specific routines

		// Number of characters so far in this 'packet'
		int a_count;

		// Set up the 'byte output' routine
		void char_init() {
			a_count = 0;
		}

		// Define the storage for the packet accumulator
		byte[] accum = new byte[256];

		// Add a character to the end of the current packet, and if it is 254
		// characters, flush the packet to disk.
		void char_out(byte c, OutputStream outs) throws IOException {
			accum[a_count++] = c;
			if (a_count >= 254)
				flush_char(outs);
		}

		// Flush the packet to disk, and reset the accumulator
		void flush_char(OutputStream outs) throws IOException {
			if (a_count > 0) {
				outs.write(a_count);
				outs.write(accum, 0, a_count);
				a_count = 0;
			}
		}

	}

	static class GifEncoderHashitem {

		public int rgb;

		public int count;

		public int index;

		public boolean isTransparent;

		public GifEncoderHashitem(int rgb, int count, int index,
				boolean isTransparent) {
			this.rgb = rgb;
			this.count = count;
			this.index = index;
			this.isTransparent = isTransparent;
		}

	}

	// / A Hashtable that uses ints as the keys.
	// <P>
	// Use just like java.util.Hashtable, except that the keys must be ints.
	// This is much faster than creating a new Integer for each access.
	// <P>
	// <A HREF="/resources/classes/Acme/IntHashtable.java">Fetch the
	// software.</A><BR>
	// <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme
	// package.</A>
	// <P>
	// @see java.util.Hashtable

	public static class IntHashtable extends Dictionary implements Cloneable {
		// / The hash table data.
		private IntHashtableEntry table[];

		// / The total number of entries in the hash table.
		private int count;

		// / Rehashes the table when count exceeds this threshold.
		private int threshold;

		// / The load factor for the hashtable.
		private float loadFactor;

		// / Constructs a new, empty hashtable with the specified initial
		// capacity and the specified load factor.
		// @param initialCapacity the initial number of buckets
		// @param loadFactor a number between 0.0 and 1.0, it defines
		// the threshold for rehashing the hashtable into
		// a bigger one.
		// @exception IllegalArgumentException If the initial capacity
		// is less than or equal to zero.
		// @exception IllegalArgumentException If the load factor is
		// less than or equal to zero.
		public IntHashtable(int initialCapacity, float loadFactor) {
			if (initialCapacity <= 0 || loadFactor <= 0.0)
				throw new IllegalArgumentException();
			this.loadFactor = loadFactor;
			table = new IntHashtableEntry[initialCapacity];
			threshold = (int) (initialCapacity * loadFactor);
		}

		// / Constructs a new, empty hashtable with the specified initial
		// capacity.
		// @param initialCapacity the initial number of buckets
		public IntHashtable(int initialCapacity) {
			this(initialCapacity, 0.75f);
		}

		// / Constructs a new, empty hashtable. A default capacity and load
		// factor
		// is used. Note that the hashtable will automatically grow when it gets
		// full.
		public IntHashtable() {
			this(101, 0.75f);
		}

		// / Returns the number of elements contained in the hashtable.
		public int size() {
			return count;
		}

		// / Returns true if the hashtable contains no elements.
		public boolean isEmpty() {
			return count == 0;
		}

		// / Returns an enumeration of the hashtable's keys.
		// @see IntHashtable#elements
		public synchronized Enumeration keys() {
			return new IntHashtableEnumerator(table, true);
		}

		// / Returns an enumeration of the elements. Use the Enumeration methods
		// on the returned object to fetch the elements sequentially.
		// @see IntHashtable#keys
		public synchronized Enumeration elements() {
			return new IntHashtableEnumerator(table, false);
		}

		// / Returns true if the specified object is an element of the
		// hashtable.
		// This operation is more expensive than the containsKey() method.
		// @param value the value that we are looking for
		// @exception NullPointerException If the value being searched
		// for is equal to null.
		// @see IntHashtable#containsKey
		public synchronized boolean contains(Object value) {
			if (value == null)
				throw new NullPointerException();
			IntHashtableEntry tab[] = table;
			for (int i = tab.length; i-- > 0;) {
				for (IntHashtableEntry e = tab[i]; e != null; e = e.next) {
					if (e.value.equals(value))
						return true;
				}
			}
			return false;
		}

		// / Returns true if the collection contains an element for the key.
		// @param key the key that we are looking for
		// @see IntHashtable#contains
		public synchronized boolean containsKey(int key) {
			IntHashtableEntry tab[] = table;
			int hash = key;
			int index = (hash & 0x7FFFFFFF) % tab.length;
			for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
				if (e.hash == hash && e.key == key)
					return true;
			}
			return false;
		}

		// / Gets the object associated with the specified key in the
		// hashtable.
		// @param key the specified key
		// @returns the element for the key or null if the key
		// is not defined in the hash table.
		// @see IntHashtable#put
		public synchronized Object get(int key) {
			IntHashtableEntry tab[] = table;
			int hash = key;
			int index = (hash & 0x7FFFFFFF) % tab.length;
			for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
				if (e.hash == hash && e.key == key)
					return e.value;
			}
			return null;
		}

		// / A get method that takes an Object, for compatibility with
		// java.util.Dictionary. The Object must be an Integer.
		public Object get(Object okey) {
			if (!(okey instanceof Integer))
				throw new InternalError("key is not an Integer");
			Integer ikey = (Integer) okey;
			int key = ikey.intValue();
			return get(key);
		}

		// / Rehashes the content of the table into a bigger table.
		// This method is called automatically when the hashtable's
		// size exceeds the threshold.
		protected void rehash() {
			int oldCapacity = table.length;
			IntHashtableEntry oldTable[] = table;

			int newCapacity = oldCapacity * 2 + 1;
			IntHashtableEntry newTable[] = new IntHashtableEntry[newCapacity];

			threshold = (int) (newCapacity * loadFactor);
			table = newTable;

			for (int i = oldCapacity; i-- > 0;) {
				for (IntHashtableEntry old = oldTable[i]; old != null;) {
					IntHashtableEntry e = old;
					old = old.next;

					int index = (e.hash & 0x7FFFFFFF) % newCapacity;
					e.next = newTable[index];
					newTable[index] = e;
				}
			}
		}

		// / Puts the specified element into the hashtable, using the specified
		// key. The element may be retrieved by doing a get() with the same key.
		// The key and the element cannot be null.
		// @param key the specified key in the hashtable
		// @param value the specified element
		// @exception NullPointerException If the value of the element
		// is equal to null.
		// @see IntHashtable#get
		// @return the old value of the key, or null if it did not have one.
		public synchronized Object put(int key, Object value) {
			// Make sure the value is not null.
			if (value == null)
				throw new NullPointerException();

			// Makes sure the key is not already in the hashtable.
			IntHashtableEntry tab[] = table;
			int hash = key;
			int index = (hash & 0x7FFFFFFF) % tab.length;
			for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
				if (e.hash == hash && e.key == key) {
					Object old = e.value;
					e.value = value;
					return old;
				}
			}

			if (count >= threshold) {
				// Rehash the table if the threshold is exceeded.
				rehash();
				return put(key, value);
			}

			// Creates the new entry.
			IntHashtableEntry e = new IntHashtableEntry();
			e.hash = hash;
			e.key = key;
			e.value = value;
			e.next = tab[index];
			tab[index] = e;
			++count;
			return null;
		}

		// / A put method that takes an Object, for compatibility with
		// java.util.Dictionary. The Object must be an Integer.
		public Object put(Object okey, Object value) {
			if (!(okey instanceof Integer))
				throw new InternalError("key is not an Integer");
			Integer ikey = (Integer) okey;
			int key = ikey.intValue();
			return put(key, value);
		}

		// / Removes the element corresponding to the key. Does nothing if the
		// key is not present.
		// @param key the key that needs to be removed
		// @return the value of key, or null if the key was not found.
		public synchronized Object remove(int key) {
			IntHashtableEntry tab[] = table;
			int hash = key;
			int index = (hash & 0x7FFFFFFF) % tab.length;
			for (IntHashtableEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
				if (e.hash == hash && e.key == key) {
					if (prev != null)
						prev.next = e.next;
					else
						tab[index] = e.next;
					--count;
					return e.value;
				}
			}
			return null;
		}

		// / A remove method that takes an Object, for compatibility with
		// java.util.Dictionary. The Object must be an Integer.
		public Object remove(Object okey) {
			if (!(okey instanceof Integer))
				throw new InternalError("key is not an Integer");
			Integer ikey = (Integer) okey;
			int key = ikey.intValue();
			return remove(key);
		}

		// / Clears the hash table so that it has no more elements in it.
		public synchronized void clear() {
			IntHashtableEntry tab[] = table;
			for (int index = tab.length; --index >= 0;)
				tab[index] = null;
			count = 0;
		}

		// / Creates a clone of the hashtable. A shallow copy is made,
		// the keys and elements themselves are NOT cloned. This is a
		// relatively expensive operation.
		public synchronized Object clone() {
			try {
				IntHashtable t = (IntHashtable) super.clone();
				t.table = new IntHashtableEntry[table.length];
				for (int i = table.length; i-- > 0;)
					t.table[i] = (table[i] != null) ? (IntHashtableEntry) table[i]
							.clone()
							: null;
				return t;
			} catch (CloneNotSupportedException e) {
				// This shouldn't happen, since we are Cloneable.
				throw new InternalError();
			}
		}

		// / Converts to a rather lengthy String.
		public synchronized String toString() {
			int max = size() - 1;
			StringBuffer buf = new StringBuffer();
			Enumeration k = keys();
			Enumeration e = elements();
			buf.append("{");

			for (int i = 0; i <= max; ++i) {
				String s1 = k.nextElement().toString();
				String s2 = e.nextElement().toString();
				buf.append(s1 + "=" + s2);
				if (i < max)
					buf.append(", ");
			}
			buf.append("}");
			return buf.toString();
		}
	}

	static class IntHashtableEntry {
		int hash;

		int key;

		Object value;

		IntHashtableEntry next;

		protected Object clone() {
			IntHashtableEntry entry = new IntHashtableEntry();
			entry.hash = hash;
			entry.key = key;
			entry.value = value;
			entry.next = (next != null) ? (IntHashtableEntry) next.clone()
					: null;
			return entry;
		}
	}

	static class IntHashtableEnumerator implements Enumeration {
		boolean keys;

		int index;

		IntHashtableEntry table[];

		IntHashtableEntry entry;

		IntHashtableEnumerator(IntHashtableEntry table[], boolean keys) {
			this.table = table;
			this.keys = keys;
			this.index = table.length;
		}

		public boolean hasMoreElements() {
			if (entry != null)
				return true;
			while (index-- > 0)
				if ((entry = table[index]) != null)
					return true;
			return false;
		}

		public Object nextElement() {
			if (entry == null)
				while ((index-- > 0) && ((entry = table[index]) == null))
					;
			if (entry != null) {
				IntHashtableEntry e = entry;
				entry = e.next;
				return keys ? new Integer(e.key) : e.value;
			}
			throw new NoSuchElementException("IntHashtableEnumerator");
		}
	}

}
